Digital cross-connect communications network devices, such as the 1631 SX manufactured by Alcatel Network Systems, Inc., are designed to make connections between input gates on input switches and output gates on output switches. Known designs for such cross-connect devices make use of matrices to connect the input gates to the output gates. To limit the physical space and manufacturing costs of the matrices, designers seek to minimize the number of cross-connects in the matrix. This objective becomes more complicated as market demands for communications services increase. In particular, as network devices address larger markets, the devices must service more and more input and output signals. These factors exacerbate the space and cost limitation problems even more for communications matrix devices.
One matrix configuration that uses a minimal number of matrix cross-connects for a given number of input gates and output gates and that provides a potentially optimal solution is known as a "rearrangeable" matrix. For the rearrangeable matrix, the number of center stage switches must equal or exceed the number of input gates on each input switch of the matrix. In a rearrangeable matrix, there exists a set of conditions such that, although the device does not use all input gates and all output gates, an attempt to use an idle input gate and an output gate is prohibited because existing connections block the signal flow through the matrix. This may happen, for example, if existing connections already occupy at least one link in every possible path between the input and output gates in question.
In a rearrangeable network, it is always possible to unblock a flow path from an idle input gate to an idle output gate by moving existing connections in the network. The term "rearrangeable," therefore, describes the property that for a given state of a network and any given idle pair of input and output gates, the existing connections of the matrix may be reassigned to new paths, if necessary, to connect the idle pair.
Existing methods and systems for connecting inputs to outputs in rearrangeable matrices generally use a standard rearrangement technique that determines which cross-connects of the matrix to rearrange to permit a signal to flow. N.C. Paull in "Reswitching of Connection Networks," The Bell System Technical Journal, May, 1962, pp. 833-856, describes this known method for unblocking a rearrangeable matrix. This method (hereinafter referred to as Paull's Method) suffers from a major limitation. Paull's Method requires breaking some of the cross-connects and making some other of the cross-connects to rearrange matrix. This procedure takes time and results in undesirable service delays or interruptions during matrix rearrangement.
It is an object of the present invention, therefore, to provide a method and system that immediately connect idle input gates to idle output gates and, if a rearrangeably blocked condition occurs, rearrange the matrix after the immediate connection. The present invention achieves this object with a minimal amount of additional circuitry and avoids the service delays and interruptions of known reswitching methods and systems.
It is also an object of the present invention to provide a method and system that rearranges existing cross-connections through a rearrangeable matrix by immediately connecting an input gate of an input switch through the matrix to an output gate of an output switch through a dedicated or extra switching element of a center matrix switch and, if the connection causes a rearrangeably blocked condition, detecting the rearrangeably blocked condition, after which the invention executes a method for performing a "hitless roll" of the signal from the extra switching element to another switching element in the center switch by first selecting a set of switching element pairs from all of the switching elements of the center switch to form a plurality of possible connection configurations from the input switch through the center switch (excluding the dedicated switching element) to the output switch, searching for the minimum path set requiring the minimum number of rearrangements of pre-existing connections of the matrix configuration and then reswitching the matrix according to the minimum path set while maintaining all signal flow from all input gates of the input switch through the center switch and to all output gates of the output switch and removing signal flow through the dedicated switching element.